﻿using System;
using System.Numerics;

namespace MartinRL.ProjectEuler
{
    /// <summary>
    /// http://projecteuler.net/index.php?section=problems&id=15
    /// 
    /// Cheating: http://www.google.com/search?q=40+choose+20
    /// </summary>
    public static class Problem015
    {
        public static BigInteger FindTheNumberOfRoutesThroughA20X20Grid()
        {
            return 40.Choose(20);
        }
    }

    internal static class Problem015_Extensions
    {
        /// <summary>
        /// http://mathworld.wolfram.com/BinomialCoefficient.html
        /// </summary>
        public static BigInteger Choose(this int n, int k)
        {
            return n.BigFactorial() /
                   ((n - k).BigFactorial() * k.BigFactorial());
        }
    }
}